//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 进阶： 
//
// 
// 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
// 👍 1345 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head==null||head.next == null) {
            return  head;
        }
        ListNode cur=null;
        ListNode temp=head;
        //建立新的链表 然后插入到指定的值之后
        ListNode replace=new ListNode(0,null);
        while (temp!=null) {
            cur=temp.next;
            addNode(replace,temp);
            temp=cur;
        }
        return replace.next;
    }
    // 在指定数据节点的后面添加新的节点 需要一前一后指针来维护
    //插入到当前节点前面的就需要前后两个指针维护 一个指向当前节点 一个指向当前节点上一个
    public void addNode(ListNode listNode,ListNode newNode){
        ListNode dummy=listNode;
        ListNode temp=listNode.next;
        while(temp!=null&&temp.val<newNode.val){
            dummy=dummy.next;
            temp = temp.next;
        }
        newNode.next=temp;
       dummy .next = newNode;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
